package com.sheng.leetcode.year2023.month07.day19;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/07/19
 * <p>
 * 874. 模拟行走机器人<p>
 * <p>
 * 机器人在一个无限大小的 XY 网格平面上行走，从点 (0, 0) 处开始出发，<p>
 * 面向北方。该机器人可以接收以下三种类型的命令 commands ：<p>
 * -2 ：向左转 90 度<p>
 * -1 ：向右转 90 度<p>
 * 1 <= x <= 9 ：向前移动 x 个单位长度<p>
 * 在网格上有一些格子被视为障碍物 obstacles 。第 i 个障碍物位于网格点  obstacles[i] = (xi, yi) 。<p>
 * 机器人无法走到障碍物上，它将会停留在障碍物的前一个网格方块上，但仍然可以继续尝试进行该路线的其余部分。<p>
 * 返回从原点到机器人所有经过的路径点（坐标为整数）的最大欧式距离的平方。（即，如果距离为 5 ，则返回 25 ）<p>
 * 注意：<p>
 * 北表示 +Y 方向。<p>
 * 东表示 +X 方向。<p>
 * 南表示 -Y 方向。<p>
 * 西表示 -X 方向。<p>
 * <p>
 * 示例 1：<p>
 * 输入：commands = [4,-1,3], obstacles = []<p>
 * 输出：25<p>
 * 解释：<p>
 * 机器人开始位于 (0, 0)：<p>
 * 1. 向北移动 4 个单位，到达 (0, 4)<p>
 * 2. 右转<p>
 * 3. 向东移动 3 个单位，到达 (3, 4)<p>
 * 距离原点最远的是 (3, 4) ，距离为 3^2 + 4^2 = 25<p>
 * <p>
 * 示例 2：<p>
 * 输入：commands = [4,-1,4,-2,4], obstacles = [[2,4]]<p>
 * 输出：65<p>
 * 解释：机器人开始位于 (0, 0)：<p>
 * 1. 向北移动 4 个单位，到达 (0, 4)<p>
 * 2. 右转<p>
 * 3. 向东移动 1 个单位，然后被位于 (2, 4) 的障碍物阻挡，机器人停在 (1, 4)<p>
 * 4. 左转<p>
 * 5. 向北走 4 个单位，到达 (1, 8)<p>
 * 距离原点最远的是 (1, 8) ，距离为 1^2 + 8^2 = 65<p>
 * <p>
 * 提示：<p>
 * 1 <= commands.length <= 10^4<p>
 * commands[i] is one of the values in the list [-2,-1,1,2,3,4,5,6,7,8,9].<p>
 * 0 <= obstacles.length <= 10^4<p>
 * -3 * 10^4 <= xi, yi <= 3 * 10^4<p>
 * 答案保证小于 2^31<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/walking-robot-simulation">874. 模拟行走机器人</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode0874 {

    @Test
    public void test01() {
//        int[] commands = {4, -1, 3};
//        int[][] obstacles = {{0, 3}};
        int[] commands = {4, -1, 4, -2, 4};
        int[][] obstacles = {{2, 4}};
        System.out.println(new Solution().robotSim(commands, obstacles));
    }
}

class Solution {
    public int robotSim(int[] commands, int[][] obstacles) {
        // 初始向北方向，-2 ：向左转 90 度，-1 ：向右转 90 度
        int ans = 0;
        int n = commands.length;
        // 初始化机器人行走的方向
        // 0：北
        // 1：东
        // 2：南
        // 3：西
        int direction = 0;
        // 初始坐标
        int x = 0, y = 0;
        // 假设没有石头的情况下
        for (int command : commands) {
            if (command == -2) {
                // 向左转
                direction = (direction + 3) % 4;
            } else if (command == -1) {
                // 向右转
                direction = (direction + 1) % 4;
            } else {
                // 直走
                // 如果有石头，每次行走时都要判断当前道路上是否存在障碍物
                if (direction == 0) {
                    // 向北
                    int oldy = y;
                    boolean flag = true;
                    for (int[] obstacle : obstacles) {
                        if (obstacle[0] == x && obstacle[1] > oldy && obstacle[1] <= oldy + command) {
                            // 道路上存在障碍物
                            if (flag) {
                                // 第一个看到的障碍物
                                y = obstacle[1] - 1;
                                flag = false;
                            } else {
                                // 后续是否还有更接近的障碍物
                                y = Math.min(y, obstacle[1] - 1);
                            }
                        }
                    }
                    if (flag) {
                        y += command;
                    }
                } else if (direction == 1) {
                    // 向东
                    int oldx = x;
                    boolean flag = true;
                    for (int[] obstacle : obstacles) {
                        if (obstacle[1] == y && obstacle[0] > oldx && obstacle[0] <= oldx + command) {
                            // 道路上存在障碍物
                            if (flag) {
                                x = obstacle[0] - 1;
                                flag = false;
                            } else {
                                x = Math.min(y, obstacle[0] - 1);
                            }
                        }
                    }
                    if (flag) {
                        x += command;
                    }
                } else if (direction == 2) {
                    // 向南
                    int oldy = y;
                    boolean flag = true;
                    for (int[] obstacle : obstacles) {
                        if (obstacle[0] == x && obstacle[1] < oldy && obstacle[1] >= oldy - command) {
                            // 道路上存在障碍物
                            if (flag) {
                                y = obstacle[1] + 1;
                                flag = false;
                            } else {
                                y = Math.min(y, obstacle[1] + 1);
                            }
                        }
                    }
                    if (flag) {
                        y -= command;
                    }
                } else {
                    // 向西
                    int oldx = x;
                    boolean flag = true;
                    for (int[] obstacle : obstacles) {
                        if (obstacle[1] == y && obstacle[0] < oldx && obstacle[0] >= oldx - command) {
                            // 道路上存在障碍物
                            if (flag) {
                                x = obstacle[0] + 1;
                                flag = false;
                            } else {
                                x = Math.min(y, obstacle[0] + 1);
                            }
                        }
                    }
                    if (flag) {
                        x -= command;
                    }
                }
                ans = Math.max(ans, x * x + y * y);
            }
        }
        return ans;
    }
}
